import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution1054 {
    public int[] rearrangeBarcodes(int[] barcodes) {
        PriorityQueue<int[]> priorityQueue=new PriorityQueue<>((a,b)->b[1]-a[1]);
        int[] f=new int[10001];
        for (int barcode : barcodes) {
            f[barcode]++;
        }
        for (int i=0;i<=10000;i++){
            if (f[i]!=0){
                priorityQueue.offer(new int[]{i,f[i]});
            }
        }
        int[] ans=new int[barcodes.length];
        int last=-1;
        for (int i=0;i<ans.length;i++){
            int[] m=priorityQueue.poll();
            if (m[0]!=last){
                last=ans[i]=m[0];
                m[1]--;
            }else {
                int[] n=priorityQueue.poll();
                last=ans[i]=n[0];
                n[1]--;
                priorityQueue.offer(n);
            }
            priorityQueue.offer(m);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution1054().rearrangeBarcodes(new int[]{1, 1, 1, 1, 2, 2, 3, 3})));
    }
}
